/*
Copyright (C) 2001-2002 Charles Hollemeersch

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

PENTA: the whole file is freakin penta...
*/

// gl_svbsp.c shadow volume bsp

#include "quakedef.h"

int svBsp_NumCutPolys;
int svBsp_NumKeptPolys;
int svBsp_NumAddedPolys;
int svBsp_NumMissedPlanes;
int svBsp_NumMissedNodes;

//FIXME: Decent allocation
//1Meg plane pool :)
#define MAX_PLANE_POOL 65536/2
#define MAX_NODE_POOL 65536
const int POINT_ON_PLANE = 0;
const int POINT_IN_FRONT_OF_PLANE = 1;
const int POINT_BEHIND_PLANE = 2;

plane_t PlanePool[MAX_PLANE_POOL];
int planesusedpool;

svnode_t NodePool[MAX_NODE_POOL];
int nodesusedpool;

//Returns an plane, tries to find the same one as tryplane, if a match if found it return the found one.
plane_t *AllocPlane(plane_t *tryplane)
{
    if (tryplane)
    {
        int i;

        //try to fit one that fits
        for (i=0; i<planesusedpool; i++)
        {
            if ((PlanePool[i].normal[0] == tryplane->normal[0]) &&
                (PlanePool[i].normal[1] == tryplane->normal[1]) &&
                (PlanePool[i].normal[2] == tryplane->normal[2]) &&
                (PlanePool[i].dist == tryplane->dist))
            {
                return &PlanePool[i];
            }
        }
    }

    if (planesusedpool >= MAX_PLANE_POOL)
    {
        Con_Printf("Too many planes...");
        svBsp_NumMissedPlanes++;
        return NULL;
    }
    planesusedpool++;

    return &PlanePool[planesusedpool-1];
}

svnode_t *AllocNode(void)
{
    if (nodesusedpool >= MAX_NODE_POOL)
    {
        Con_Printf("Too many nodes...");
        svBsp_NumMissedNodes++;
        return NULL;
    }
    nodesusedpool++;

    return &NodePool[nodesusedpool-1];
}

/* changed a bit */
static const int PlaneClassify(float value)
{
    int offset;

    if (value < -ON_EPSILON)
    {
        offset = POINT_IN_FRONT_OF_PLANE;
    }
    else if (value > ON_EPSILON)
    {
        offset = POINT_BEHIND_PLANE;
    }
    else
    {
        offset = POINT_ON_PLANE;
    }
    return offset;
}

/*
=============
R_CreateEmptyTree

Do some tricks to make sure we have a 360 deg. field of view.
This routine destroys the last svbsp the program has generated.

         plane
         /   \
      -plane  open
       /  \
   solid   open

=============
*/
svnode_t *R_CreateEmptyTree(void)
{
    plane_t *plane1;
    plane_t *plane2;
    svnode_t *node1;
    svnode_t *node2;

    planesusedpool = 0;
    nodesusedpool = 0;
    svBsp_NumMissedPlanes = 0;
    svBsp_NumMissedNodes = 0;

    plane1 = AllocPlane (NULL);
    plane2 = AllocPlane (NULL);
    node1 = AllocNode ();
    node2 = AllocNode ();

    //all planes go trough the light origin
    plane1->normal[0] = 1;
    plane1->normal[1] = 0;
    plane1->normal[2] = 0;
    plane1->dist = DotProduct (currentshadowlight->origin, plane1->normal);

    plane2->normal[0] = -1;
    plane2->normal[1] = 0;
    plane2->normal[2] = 0;
    plane2->dist = DotProduct (currentshadowlight->origin, plane2->normal);


    node1->splitplane = plane1;
    node1->children[0] = node2;
    node1->children[1] = NULL;

    node2->splitplane = plane2;
    node2->children[0] = NULL;
    node2->children[1] = NULL;

    return node1;
}

#define MAX_POLY_VERT 32
void SplitPolygon(vec3_t *polygon,int *signs, int vnum, plane_t *plane, vec3_t *inpts, int *innum, vec3_t *outpts, int *outnum)
{
    int     out_c = 0;
    int     in_c = 0;
    vec3_t  *ptA = &polygon[vnum-1];
    vec3_t  *ptB, v, newVert;
    int     sideA = signs[vnum-1];
    int     sideB;
    int     i;
    float   sect;

    for (i=0;  i<vnum; i++)
    {
        ptB = &polygon[i];
        sideB = signs[i];

        //is b on "right side"
        if (sideB == POINT_BEHIND_PLANE)
        {
            if (sideA == POINT_IN_FRONT_OF_PLANE)
            {
                // compute the intersection point of the line
                // from point A to point B with the partition
                // plane. This is a simple ray-plane intersection.
                VectorSubtract ((*ptB), (*ptA), v);
                sect = - (DotProduct (plane->normal, (*ptA) )-plane->dist) / DotProduct (plane->normal, v);
                VectorScale (v,sect,v);

                //add a new vertex
                VectorAdd ((*ptA), v, newVert);
                VectorCopy (newVert, inpts[in_c]);
                VectorCopy (newVert, outpts[out_c]);

                out_c++;
                in_c++;
            }
            VectorCopy (polygon[i], outpts[out_c]);
            out_c++;
        }
        //b is on "left" side
        else if (sideB == POINT_IN_FRONT_OF_PLANE)
        {
            if (sideA == POINT_BEHIND_PLANE)
            {
                // compute the intersection point of the line
                // from point A to point B with the partition
                // plane. This is a simple ray-plane intersection.
                VectorSubtract ((*ptB), (*ptA), v);
                sect = - (DotProduct (plane->normal, (*ptA) )-plane->dist) / DotProduct (plane->normal, v);
                VectorScale (v,sect,v);

                //add a new vertex
                VectorAdd ((*ptA), v, newVert);
                VectorCopy (newVert, inpts[in_c]);
                VectorCopy (newVert, outpts[out_c]);

                out_c++;
                in_c++;
            }
            VectorCopy (polygon[i], inpts[in_c]);
            in_c++;
        }
        //b is almost on plane
        else
        {

            VectorCopy (polygon[i], inpts[in_c]);
            VectorCopy (inpts[in_c], outpts[out_c]);
            in_c++;
            out_c++;
        }
        ptA = ptB;
        sideA = sideB;

        if ((out_c > MAX_POLY_VERT) || (in_c > MAX_POLY_VERT))
        {
            Con_Printf ("MAX_POLY_VERT exceeded: %i %i\n", in_c, out_c);

            //just return what we've got
            (*innum) = in_c;
            (*outnum) = out_c;
            return;
        }
    }
    (*innum) = in_c;
    (*outnum) = out_c;
}

/*
=============
R_AddShadowCaster

Polygons must be added in front to back order!
=============
*/
svnode_t *R_AddShadowCaster(svnode_t *node, vec3_t *v, int vnum, msurface_t *surf,int depth)
{
    int     sign;
    int	    signs[MAX_POLY_VERT],signs2[MAX_POLY_VERT];
    vec3_t  v1[MAX_POLY_VERT],v2[MAX_POLY_VERT];
    int     vnum1, vnum2;
    int     i;

    if (depth > 1500)
    {
        Con_Printf("to deep\n");
        return NULL;
    }

    if (vnum == 0)
    {
        return NULL;
    }
    sign = 0;

    for (i=0; i<vnum; i++)
    {
        sign |= signs[i] = PlaneClassify (DotProduct (v[i], node->splitplane->normal)- node->splitplane->dist);
    }

    if (sign == 1)
    {
        if (node->children[0] != NULL)
        {

            R_AddShadowCaster (node->children[0], v, vnum, surf, depth+1);
        }
        else
        {

            svBsp_NumCutPolys++;
        }
    }
    else if (sign == 2)
    {
        if (node->children[1] != NULL)
        {
            R_AddShadowCaster (node->children[1], v, vnum, surf, depth+1);
        }
        else
        {
            node->children[1] = ExpandVolume(v, signs, vnum, surf);

            if (surf->visframe != r_lightTimestamp)
            {
                //Store it out as visible
                surf->shadowchain = shadowchain;
                surf->visframe = r_lightTimestamp;
                surf->polys->lightTimestamp = r_lightTimestamp;
                shadowchain = surf;
                svBsp_NumKeptPolys++;
            }
        }
    }
    else if (sign == 3)
    {
        SplitPolygon(&v[0], &signs[0], vnum, node->splitplane, &v1[0], &vnum1, &v2[0], &vnum2);

        if (node->children[0] != NULL)
        {
            R_AddShadowCaster (node->children[0], v1, vnum1, surf, depth + 1);
        }
        else
        {
            svBsp_NumCutPolys++;
        }

        if (vnum2 == 0)
        {
            return NULL;
        }

        if (node->children[1] != NULL)
        {
            R_AddShadowCaster (node->children[1], v2, vnum2, surf, depth+1);
        }
        else
        {
            node->children[1] = ExpandVolume (v2, signs2, vnum2, surf);

            if (surf->visframe != r_lightTimestamp)
            {
                //Store it out as visible
                surf->shadowchain = shadowchain;
                surf->visframe = r_lightTimestamp;
                surf->polys->lightTimestamp = r_lightTimestamp;
                shadowchain = surf;
                svBsp_NumKeptPolys++;
            }
        }
    }
    return NULL;
}

/*
=============
ExpandVolume

=============
*/
svnode_t *ExpandVolume(vec3_t *v,int *sign, int vnum, msurface_t *surf)
{
    svnode_t	*res, *currnode;
    int		    i;

#ifdef SHADOW_DEBUG
    Con_Printf ("expanding volume %i\n", vnum);
#endif

    if (vnum == 0)
    {
        return NULL;
    }
    res = NodeFromEdge (v, vnum, 0);

    if (!res)
    {
        return NULL;
    }
    currnode = res;

    for (i=1; i<vnum; i++)
    {
        currnode->children[0] = NodeFromEdge (v, vnum, i);
        if (currnode->children[0] == NULL) break;
        currnode = currnode->children[0];
    }
    return res;
}

/*
=============
NodeFromEdge
=============
*/
svnode_t *NodeFromEdge(vec3_t *v, int vnum, int edgeindex)
{
    vec3_t		*v1,*v2;
    vec3_t		vert1,vert2,normal;
    vec_t		dist;
    plane_t		*plane, tryplane;
    svnode_t	*res;

    //Extract one vertex so we can calultate the normal of this shadow plane
    v1 = &v[edgeindex];
    v2 = &v[(edgeindex+1)% vnum];
    VectorSubtract ((*v1), currentshadowlight->origin, vert1);

    VectorSubtract ((*v1), (*v2), vert2);

    CrossProduct (vert1, vert2, normal);
    Normalize (normal);

    //VectorInverse(normal);
    dist = DotProduct(normal, currentshadowlight->origin);

    //make a node with it
    VectorCopy (normal, tryplane.normal);
    tryplane.dist = dist;

    plane = AllocPlane (&tryplane);

    // probably redundant as it allready is == NULL if not found
    if (!plane)
    {
        return NULL;
    }
    VectorCopy (normal, plane->normal);
    plane->dist = dist;

    res = AllocNode ();

    // probably redundant as it allready is == NULL if not found
    if (!res)
    {
        return NULL;
    }
    res->splitplane = plane;

    res->children[0] = NULL;
    res->children[1] = NULL;

    return res;
}
